#include <queue>
using namespace std;
struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int minDepth(TreeNode *root)
{
    if (root == nullptr)
        return 0;
    int m1 = minDepth(root->left);
    int m2 = minDepth(root->right);
    return root->left == nullptr || root->right == nullptr ? m1 + m2 + 1 : min(m1, m2) + 1;
}

class Solution
{
public:
    int minDepth(TreeNode *root)
    {
        queue<TreeNode *> que;
        if (root == NULL)
            return 0;
        que.push(root);
        int minDep = 1;
        while (!que.empty())
        {
            int size = que.size();
            while (size--)
            {
                TreeNode *node = que.front();
                que.pop();
                if (!node->left && !node->right)
                {
                    return minDep;
                }
                if (node->left)
                    que.push(node->left);
                if (node->right)
                    que.push(node->right);
            }
            minDep += 1;
        }
        return minDep;
    }
};